#ifndef KTGROUPEDVECTOR_H
#define KTGROUPEDVECTOR_H

#include <vector>
#include <cassert>
#include <algorithm>

// 一维容器实现的分组序列
// 分组序列也可看做变长数组之序列

// 若T传入void类型，则不分配元素存储空间，仅同步各分组元素的位置（索引）信息
template<typename T = void>
class KtGroupedVector
{
public:
    using container_t = std::conditional_t<std::is_void_v<T>, void*, std::vector<T>>;

    // 为一维容器预留空间@room
    // TODO: void reserve(unsigned room);

    // 返回分组数
    auto groups() const { return gvPos_.size(); }

    // 返回各分组所含元素的总个数
    auto totalSize() const { return gvPos_.empty() ? 0 : gvPos_.back(); }

    // 返回第@groupIdx分组的元素个数
    auto groupSize(unsigned groupIdx) const {
        assert(groupIdx < groups());
        auto lastPos = gvPos_[groupIdx];
        return groupIdx == 0 ? lastPos : lastPos - gvPos_[groupIdx - 1];
    }

    // 返回@groupIdx分组在一维容器中的起始位置（索引）
    auto groupStartPos(unsigned groupIdx) const {
        assert(groupIdx <= groups());
        return groupIdx == 0 ? 0 : gvPos_[groupIdx - 1];
    }

    // 返回@groupIdx分组在一维容器中的终止位置（索引），即最后一个元素的下一个位置（索引）
    auto groupEndPos(unsigned groupIdx) const {
        assert(groupIdx < groups());
        return gvPos_[groupIdx];
    }

    // 返回第@groupIdx分组的第@itemIdx元素在一维容器中的位置（索引）
    auto itemPos(unsigned groupIdx, unsigned itemIdx) const {
        assert(groupIdx < groups() && itemIdx < groupSize(groupIdx));
        return groupStartPos(groupIdx) + itemIdx;
    }

    // map item position(row) to group index
    auto itemGroup(int pos) const {
        assert(pos < totalSize());
        auto iter = std::upper_bound(gvPos_.cbegin(), gvPos_.cend(), pos);
        return std::distance(gvPos_.cbegin(), iter);
    }

    // 新增分组，排在末尾
    // @initSize: 分组的初始大小
    void appendGroup(int initSize = 0) {
        assert(initSize >= 0);
        gvPos_.push_back(gvPos_.empty() ? initSize : gvPos_.back() + initSize);
    }

    // 新增分组，在第@groupPos分组的位置插入
    void insertGroup(unsigned groupPos) {
        assert(groupPos <= groups());
        auto pos = std::next(gvPos_.cbegin(), groupPos);
        gvPos_.insert(pos, groupStartPos(groupPos));
        // NB: 由于未实际插入元素，所以不须更新gvPos_数据
    }

    // 移除第@groupIdx分组
    void removeGroup(unsigned groupIdx) {
        assert(groupIdx < groups());
        auto pos = std::next(gvPos_.cbegin(), groupIdx);
        auto diff = groupSize(groupIdx);
        gvPos_.erase(pos);
        offsetPos_(groupIdx, -diff);
    }

    // 调整第@groupIdx分组的元素数量为@size
    // TODO: void resize(unsigned groupIdx, unsigned newSize);

    // 在第@groupIdx分组的第@itemPos位置插入元素
    void insertItem(unsigned groupIdx, unsigned itemPos) {
        assert(itemPos <= groupSize(groupIdx));
        offsetPos_(groupIdx, 1);
    }

    // 在第@groupIdx分组的末尾插入元素
    void appendItem(unsigned groupIdx) {
        insertItem(groupIdx, groupSize(groupIdx));
    }

    // 移除第@groupIdx分组的第@itemIdx元素
    void removeItem(unsigned groupIdx, unsigned itemIdx) {
        assert(itemIdx < groupSize(groupIdx));
        offsetPos_(groupIdx, -1);
    }

    void clear() {
        gvPos_.clear();
    }

private:

    // 帮助函数：从gvPos_的第@idx成员开始，对各元素进行偏移运算，偏移量为@diff
    void offsetPos_(unsigned idx, int diff) {
        for(unsigned i = idx; i < gvPos_.size(); i++)
            gvPos_[i] += diff;
    }

private:
    std::vector<int> gvPos_; // 各分组的最后一个元素在一维容器中的下一个位置（索引）
    container_t vbuf_; // 存储各分组的一维容器
};

#endif // KTGROUPEDVECTOR_H
